// 二分查找 - 利用数组的 二段性 解决问题，每次可以舍弃一段数据
// 经典在 有序数组 中找一个数的问题，都可以使用二分查找
// 下面的题目虽然是找一个区间，但是要求时间复杂度为 O(log n)，因此确定用二分法
// 找一个区间的左右端点，可以借鉴使用二分法找一个数，先找区间左端点，再找区间右端点

// 例题 2：
// 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
// 请你找出给定目标值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]。
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//
//        示例 1：
//
//        输入：nums = [5,7,7,8,8,10], target = 8
//        输出：[3,4]
//        示例 2：
//
//        输入：nums = [5,7,7,8,8,10], target = 6
//        输出：[-1,-1]
//        示例 3：
//
//        输入：nums = [], target = 0
//        输出：[-1,-1]
//
//
//        提示：
//
//        0 <= nums.length <= 105
//        -109 <= nums[i] <= 109
//        nums 是一个非递减数组
//        -109 <= target <= 109

// 解题思路：
// 找左端点
// 左中点：mid = left + (right - left) / 2
// x < target: left = mid + 1;
// x >= target: right = mid

// 找右端点
// 右中点：mid = left + (right - left + 1) / 2
// x > target: right = mid - 1;
// x<= target: left = mid;

// 注意： 当 nums[left] == nums[right]
// 判断找到的 nums[left] 或者 nums[right] 是否等于 target
// 如果等于，则表示找到了，不等于则没找到；

public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int n = nums.length;
        if(n == 0) return ret;
        // 找左端点
        int left = 0; int right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if(nums[left] == target) ret[0] = right;
        else return ret;
        // 找右端点
        left = 0; right = n - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        if(nums[right] == target) ret[1] = left;
        else return ret;

        return ret;
    }
}
